/**
 * ExpressionTree represents an expression tree of operators and operands.
 * 
 * @author Lewis and Chase
 * @version 4.0
 */
public class ExpressionTree extends LinkedBinaryTree<ExpressionTreeOp>
{
	ArrayUnorderedList<Step> stepList;
	int stepCount = 0;
	
    /**
     * Creates an empty expression tree.
     */
    public ExpressionTree() 
    {
        super();
    }

    /**
     * Constructs a expression tree from the two specified expression 
     * trees.
     *
     * @param element      the expression tree for the center
     * @param leftSubtree  the expression tree for the left subtree
     * @param rightSubtree the expression tree for the right subtree
     */
    public ExpressionTree(ExpressionTreeOp element,
                    ExpressionTree leftSubtree, ExpressionTree rightSubtree) 
    {
        root = new BinaryTreeNode<ExpressionTreeOp>(element, leftSubtree, rightSubtree);
    }
    
    /**
     * Evaluates the expression tree by calling the recursive 
     * evaluateNode method.
     *
     * @return the integer evaluation of the tree
     */
    public int evaluateTree() 
    {
    	stepCount = 0;
    	stepList = new ArrayUnorderedList<Step>(); 
        return evaluateNode(root);
    }

    /**
     * Recursively evaluates each node of the tree.
     *
     * @param root the root of the tree to be evaluated
     * @return the integer evaluation of the tree
     */
    public int evaluateNode(BinaryTreeNode<ExpressionTreeOp> root) 
    {
        int result, operand1, operand2;
        ExpressionTreeOp temp;
        
        if (root==null)
            result = 0;
        else
        {
            temp = (ExpressionTreeOp)root.getElement();
            
            if (temp.isOperator())
            {
                operand1 = evaluateNode(root.getLeft());
                operand2 = evaluateNode(root.getRight());
                result = computeTerm(temp.getOperator(), operand1, operand2);
                stepCount++;
                Dependent dependent = getDependent(
                		root.getLeft().getElement(), root.getRight().getElement()
                		);
                Step step = new Step(stepCount, operand1, operand2, temp.getOperator(), result, dependent);
                temp.setStep(step);
                recordComputeStep(step);
            }
            else
                result = temp.getValueInInt();
        }
        return result;
    }
    
    private Dependent getDependent(ExpressionTreeOp left, ExpressionTreeOp right){
    	Dependent dependent = null;
    	if (left.hasStep() && right.hasStep()){
    		dependent = new Dependent(left.getStep().getStepNumber(), right.getStep().getStepNumber(), Dependent.isLeftAndRight);
        }else{
        	if (left.hasStep()){
        		dependent = new Dependent(left.getStep().getStepNumber(), Dependent.isLeft);
        	}
        	if (right.hasStep()){
            	if (dependent == null){
            		dependent = new Dependent(right.getStep().getStepNumber(), Dependent.isRight);
            	}
            	else{
            		dependent.setSecondStep(right.getStep().getStepNumber());
            		dependent.setDirection(Dependent.isLeftAndRight);
            	}
            }
        }
    	return dependent;
    }

    /**
     * Evaluates a term consisting of an operator and two operands.
     *
     * @param operator  the operator for the expression
     * @param operand1  the first operand for the expression
     * @param operand2  the second operand for the expression
     */
    private static int computeTerm(char operator, int operand1, int operand2)
    {
        int result=0;
        
        if (operator == '+')
            result = operand1 + operand2;
        
        else if (operator == '-')
            result = operand1 - operand2;
        else if (operator == '*')
            result = operand1 * operand2;
        else 
            result = operand1 / operand2;

        return result;
    }
    
    /**
     * Generates a list of computation step of evaluates the binary tree
     * @return a string representative of the computation step list
     */
    public String getComputeStep(){
    	String result = "";
    	int count = 0;
    	while (!stepList.isEmpty()){
    		if (stepList.get(count) == null) break;
    		result += stepList.get(count).toString() + "\n";
    		count++;
    	}
    	return result;
    }
    
    private void recordComputeStep(Step step){
    	stepList.addToRear(step);
    }
    
    /**
     * Return the list if computation step
     * @return list of computation step in this ExpressionTree
     */
    public ArrayUnorderedList<Step> getComputerStepList(){
    	return stepList;
    }
    
    /**
     * Generates a structured string version of the tree by performing 
     * a level order traversal.
     *
     * @return a string representative of this binary tree
     */
    public String printTree()
    {
        return printTree(root, "     ");
    }
    
    private String printTree(BinaryTreeNode<ExpressionTreeOp> r, String strIndent){
    	if (r == null) return "";
    	String result = "";
    	result += printTree(r.getRight(), strIndent+"     ");
    	result += strIndent + r.getElement().toString()+"\n";
    	result += printTree(r.getLeft(), strIndent+"     ");
    	return result;
    }
    
    /**
     * Generates a string in post order of the element
     * @param isInclude if yes, the post order will include variable, otherwise it will using the variable value
     * @return a string representation of the post order
     */
    public String postOrderIncludeVariable(boolean isInclude){
    	if (isInclude)
    		return postOrderIncludeVariable(root);
    	else 
    		return postOrderIncludeValue(root); 
    }
    
    private String postOrderIncludeVariable(BinaryTreeNode<ExpressionTreeOp> r){
    	if (r == null) return "";
    	String result = "";
    	result += postOrderIncludeVariable(r.getLeft());
    	result += postOrderIncludeVariable(r.getRight());
    	result += r.getElement().toStringInCharacter();
    	return result;
    }
    
    private String postOrderIncludeValue(BinaryTreeNode<ExpressionTreeOp> r){
    	if (r == null) return "";
    	String result = "";
    	result += postOrderIncludeVariable(r.getLeft());
    	result += postOrderIncludeVariable(r.getRight());
    	result += r.getElement().toString();
    	return result;
    }
}

